﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using ControlNode;

namespace ClassLibrary
{
    public class Dijkstra
    {
        private int[,] ConvertLinksToProcessableTable(List<Link> links, out String[] intToNodeNameMap, out Dictionary<String, int> nodeNameToIntMap, out int[,] portTable)
        {
            int[,] processableTable;

            nodeNameToIntMap = new Dictionary<string, int>();

            int nodesCount;

            foreach (var link in links)
            {
                if (!nodeNameToIntMap.ContainsKey(link.EndPoint1.Id))
                {
                    int nextIdx = nodeNameToIntMap.Count;
                    String nextNodeName = link.EndPoint1.Id;
                    nodeNameToIntMap.Add(nextNodeName, nextIdx);
                }
                if (!nodeNameToIntMap.ContainsKey(link.EndPoint2.Id))
                {
                    int nextIdx = nodeNameToIntMap.Count;
                    String nextNodeName = link.EndPoint2.Id;
                    nodeNameToIntMap.Add(nextNodeName, nextIdx);
                }
            }

            nodesCount = nodeNameToIntMap.Count;

            intToNodeNameMap = new string[nodesCount];
            foreach (var v in nodeNameToIntMap)
            {
                intToNodeNameMap[v.Value] = v.Key;
            }

            processableTable = new int[nodesCount, nodesCount];
            portTable = new int[nodesCount, nodesCount];

            for (int i = 0; i < nodesCount; i++)
            {
                for (int j = 0; j < nodesCount; j++)
                {
                    processableTable[i, j] = INF;
                }
            }

            foreach (var link in links)
            {
                int idx1 = nodeNameToIntMap[link.EndPoint1.Id];
                int idx2 = nodeNameToIntMap[link.EndPoint2.Id];

                processableTable[idx1, idx2] = 1;
                processableTable[idx2, idx1] = 1;

                portTable[idx1, idx2] = link.EndPoint1.PortId;
                portTable[idx2, idx1] = link.EndPoint2.PortId;
            }

            for (int i = 0; i < nodesCount; i++)
            {
                Console.WriteLine(i + " " + intToNodeNameMap[i]);
            }

            for (int j = 0; j < nodesCount; j++)
            {
                Console.Write("\t" + j );
            }

            Console.WriteLine();

            for (int i = 0; i < nodesCount; i++)
            {
                Console.Write(i + "\t");
                for (int j = 0; j < nodesCount; j++)
                {
                    Console.Write(processableTable[i, j] + "\t");
                }
                Console.WriteLine();
            }

            return processableTable;
        }


        public const int INF = 1000000;
        public int[,] Graph { get; set; }
        public Dijkstra()
        {
        }

        public SNPP[] dijkstra(List<Link> links, String s, String d)
        {
            String[] intToNodeNameMap;
            Dictionary<String, int> nodeNameToIntMap;
            int[,] portTable;
            Graph = ConvertLinksToProcessableTable(links, out intToNodeNameMap, out nodeNameToIntMap, out portTable);

            int[] path = GetPath(nodeNameToIntMap[s], nodeNameToIntMap[d]);

            String[] pathByName = new string[path.Count()];

            for (int i = 0; i < path.Count(); i++)
            {
                pathByName[i] = intToNodeNameMap[path[i]];
            }

            SNPP[] snpps = new SNPP[(path.Count() - 1) * 2];
            

            snpps[0] = new SNPP(pathByName[0], portTable[path[0], path[1]]);
            for (int i = 1; i < path.Count() - 1; i++)
            {
                snpps[i * 2 - 1] = new SNPP(pathByName[i], portTable[path[i], path[i - 1]]);
                snpps[i * 2] = new SNPP(pathByName[i], portTable[path[i], path[i + 1]]);
            }
            snpps[snpps.Count() - 1] = new SNPP(pathByName[path.Count() - 1], portTable[path[path.Count() - 1], path[path.Count() - 2]]);

            Logger.SetText(path[0] + " " + pathByName[0] + " port:" + portTable[path[0], path[1]]);
            
            for (int i = 1; i < path.Count() - 1; i++)
            {
                Logger.SetText(" -> port:" + portTable[path[i], path[i - 1]] + " / " + path[i] + " " + pathByName[i] + " port:" + portTable[path[i], path[i + 1]]);
            }

            Logger.SetText(" -> port:" + portTable[path[path.Count() - 1], path[path.Count() - 2]] + " / " + path[path.Count() - 1] + " " + pathByName[path.Count() - 1]);

            return snpps;
        }

        public int[] GetPath(int SRC, int DEST)
        {
            int graphSize = Graph.GetLength(0);
            int[] dist = new int[graphSize];
            int[] prev = new int[graphSize];
            int[] nodes = new int[graphSize];

            for (int i = 0; i < dist.Length; i++)
            {
                dist[i] = prev[i] = INF;
                nodes[i] = i;
            }

            dist[SRC] = 0;
            do
            {
                int smallest = nodes[0];
                int smallestIndex = 0;
                for (int i = 1; i < graphSize; i++)
                {
                    if (dist[nodes[i]] < dist[smallest])
                    {
                        smallest = nodes[i];
                        smallestIndex = i;
                    }
                }
                graphSize--;
                nodes[smallestIndex] = nodes[graphSize];

                if (dist[smallest] == INF || smallest == DEST)
                    break;

                for (int i = 0; i < graphSize; i++)
                {
                    int v = nodes[i];
                    int newDist = dist[smallest] + Graph[smallest, v];
                    if (newDist < dist[v])
                    {
                        dist[v] = newDist;
                        prev[v] = smallest;
                    }
                }
            } while (graphSize > 0);
            return ReconstructPath(prev, SRC, DEST);
        }


        public int[] ReconstructPath(int[] prev, int SRC, int DEST)
        {
            int[] ret = new int[prev.Length];
            int currentNode = 0;
            ret[currentNode] = DEST;
            while (ret[currentNode] != INF && ret[currentNode] != SRC)
            {
                ret[currentNode + 1] = prev[ret[currentNode]];
                currentNode++;
            }
            if (ret[currentNode] != SRC)
                return null;
            int[] reversed = new int[currentNode + 1];
            for (int i = currentNode; i >= 0; i--)
                reversed[currentNode - i] = ret[i];
            return reversed;
        }

    }
}
